﻿#include "LinkedList.h"

//2.初始化链表；
struct LinkedNode* Init_LinkList()
{
	struct LinkedNode* header = malloc(sizeof(struct LinkedNode));
	header->data = -1;
	header->next = NULL;

	//9.尾部指针；
	struct LinkedNode* pRear = header;
	int val = -1;
	while (true)
	{
		printf("8.输入要插入链表结点的值：\n");
		scanf("%d", &val);
		if (val == -1)
		{
			break;
		}

		//10.先创建新结点；
		struct LinkedNode* newNode = malloc(sizeof(struct LinkedNode));
		newNode->data = val;
		newNode->next = NULL;

		//11.新结点插入到链表中；
		pRear->next = newNode;

		//12.更新尾部指针指向；
		pRear = newNode;
	}
	return header;
}
//3.在值为oldVal的结点数据位置处，插入一个新的结点数据newVal；
void InsertByValue_LinkList(struct LinkedNode* header, int oldVal, int newVal)
{
	if (NULL == header)
	{
		return;
	}
	//16.两个辅助指针变量，pPrev前一个结点指针，pCurrent当前结点指针；
	struct LinkedNode* pPrev = header;
	struct LinkedNode* pCurrent = pPrev->next;
	while (pCurrent != NULL)
	{
		if (pCurrent->data == oldVal)
		{
			break;
		}
		pPrev = pCurrent;
		pCurrent = pCurrent->next;
	}
	//25.当链表中不存在oldVal的结点时，直接将newVal插入到链表末尾；
#if 0
	//17.如果pCurrent为NULL，说明链表中不存在值为oldVal的结点；
	if (pCurrent == NULL)
	{
		return;
	}
#endif

	//18.先创建新结点；
	struct LinkedNode* newNode = malloc(sizeof(struct LinkedNode));
	newNode->data = newVal;
	newNode->next = NULL;

	//19.新结点插入到链表中；
	newNode->next = pCurrent;
	pPrev->next = newNode;
}
//4.删除值为delVal的结点数据；
void RemoveByValue_LinkList(struct LinkedNode* header, int delVal)
{
	if (NULL == header)
	{
		return;
	}
	//27.两个辅助指针变量，pPrev前一个结点指针，pCurrent当前结点指针；
	struct LinkedNode* pPrev = header;
	struct LinkedNode* pCurrent = pPrev->next;
	while (pCurrent != NULL)
	{
		if (pCurrent->data == delVal)
		{
			break;
		}
		//28.移动两个辅助指针；
		pPrev = pCurrent;
		pCurrent = pCurrent->next;
	}
	if (NULL == pCurrent)
	{
		return;
	}
	//29.重新建立待删除结点的前驱结点，和后继结点的关系；
	pPrev->next = pCurrent->next;
	//30.释放删除结点内存；
	free(pCurrent);
	pCurrent = NULL;
}
//5.遍历链表；
void Foreach_LinkList(struct LinkedNode* header)
{
	if (NULL == header)
	{
		return;
	}
	//13.辅助指针变量；
	struct LinkedNode* pCurrent = header->next;
	while (pCurrent != NULL)
	{
		printf("14.输出当前结点的值data为：%d\n", pCurrent->data);
		pCurrent = pCurrent->next;
	}
}
//6.销毁链表；
void Destroy_LinkList(struct LinkedNode* header)
{
	if (NULL == header)
	{
		return;
	}
	//30.辅助指针变量pCurrent；
	struct LinkedNode* pCurrent = header->next;
	while (pCurrent != NULL)
	{
		//21.先保存当前结点的下一个结点地址；
		struct LinkedNode* pNext = pCurrent->next;
		//22.释放当前结点内存；
		printf("33.当前值为%d的结点被销毁！\n", pCurrent->data);//111,311,411
		free(pCurrent);
		//23.pCurrent指向下一个结点；
		pCurrent = pNext;
	}
}
//7.清空链表；
void Clear_LinkList(struct LinkedNode* header)
{
	if (NULL == header)
	{
		return;
	}
	//20.辅助指针变量pCurrent；
	struct LinkedNode* pCurrent = header->next;
	while (pCurrent != NULL)
	{
		//21.先保存当前结点的下一个结点地址；
		struct LinkedNode* pNext = pCurrent->next;
		//22.释放当前结点内存；
		free(pCurrent);
		//23.pCurrent指向下一个结点；
		pCurrent = pNext;
	}
	header->next = NULL;
}

//34.链表逆序；
void Reverse_LinkList(struct LinkedNode* header)
{
	if (NULL == header)
	{
		return;
	}
	struct LinkedNode* pPrev = NULL;
	struct LinkedNode* pCurrent = header->next;
	struct LinkedNode* pNext = NULL;

	while (pCurrent != NULL)
	{
		//35.pNext指向第三个结点；pCurrent指向第二个结点，让pCurrent的next指向null，即第二个结点的next为null，
			//header头结点为末尾；
		pNext = pCurrent->next;
		pCurrent->next = pPrev;

		//36.将pPrev指向第二结点，pCurrent指向第三个结点,就是将pCurrent向后移动一个结点；
		pPrev = pCurrent;
		pCurrent = pNext;
	}

	//37.执行第二遍时，pNext指向第四个结点，pCurrent指向第三个结点，pCurrent的next指向指向第二个结点，即第二个结
		//点指向第三个结点；然后pPrev指向第三个结点，pCurrent指向第四个结点。执行到最后一次时，pNext指向null，
		//pCurrent的next指向倒2结点；pPrev指向尾结点，pCurrent指向null。此时，第二个结点指向null，尾结点的next
		//指向倒2，已经基本实现逆序。下面一步，实现第一个结点指向尾结点，第二个结点处断开了；a,b,c->bca->acb
	//40.需要注意的是，头结点header在链表中，没有实际意义，只是个标识符，表示从header的next开始算起，即第二个结
		//点才是真正意义上的头结点。header,a,b,c,d-->header  a,b,c,d-->header.d,c,b,a。因此，每次遍历时，都是从
		//a,b,c,d开始遍历，而不是从header。
	header->next = pPrev;
}